GATE PYQ

GATE CSE 2016 SET-2

Q21.
Let A1,A2,A3, and A4 be four matrices of dimensions 10x5, 5x20, 20x10, and 10x5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is __________.

Q22.
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .

Q23.
The minimum number of colours that is sufficient to vertex-colour any planar graph is _________.

Q24.
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .

Q25.
Consider thefollowingprogram: int f(int*p, int n) { if (n<=1)return0; else returnmax(f(p+1,n-1),p[0]-p[1]); } int main() { int a[]={3,5,2,6,4}; printf("%d", f(a,5)); } Note: max(x,y) returns the maxi mumof x and y. The value printed by this program is____________ .

Q26.
The value printed by the following program is . void f(intp, int m){ m =m+5; p =*p+m; return; } void main(){ int i=5, j=10; f(&i, j); printf("%d", i+j); }

Q27.
A complete binary min-heap is made by including each integer in [1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is_____. .

Q28.
Consider an eight-bit ripple-carry Combinational Circuit for computing the sum of A and B, where A and B are integers represented in 2's complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is ________.

Q29.
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: \Theta(N) \; delete , O(logN) \; insert , O(logN) \; find , and \Theta(N) \; decrease-key. What is the time complexity of all these operations put together?

Q30.
Consider the systems,each consisting of m linear equations in n variables. I. If m \lt n, then all such systems have a solution II. If m \gt n, then none of these systems has a solution III. If m = n, then there exists a system which has a solution Which one of the following is CORRECT?